//给你两个二进制字符串，返回它们的和（用二进制表示）。 
//
// 输入为 非空 字符串且只包含数字 1 和 0。 
//
// 
//
// 示例 1: 
//
// 输入: a = "11", b = "1"
//输出: "100" 
//
// 示例 2: 
//
// 输入: a = "1010", b = "1011"
//输出: "10101" 
//
// 
//
// 提示： 
//
// 
// 每个字符串仅由字符 '0' 或 '1' 组成。 
// 1 <= a.length, b.length <= 10^4 
// 字符串如果不是 "0" ，就都不含前导零。 
// 
// Related Topics 数学 字符串 
// 👍 461 👎 0

package leetcode.editor.cn;

//Java：二进制求和
public class P67AddBinary {

    /**
     *
     * 思路：新建一个字符数组，字符串末尾相加，大于2的有进位标识，相加的时候要注意进位。
     *
     * 执行用时： 2 ms , 在所有 Java 提交中击败了 98.75% 的用户 内存消耗： 38.4 MB , 在所有 Java 提交中击败了 64.97% 的用户
     *
     */
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        // 0 333
        public String addBinary(String a, String b) {
            int lenA = a.length();
            int lenB = b.length();
            char[] ch = new char[lenA > lenB ? lenA : lenB];

            int i = lenA - 1;
            int k = lenB - 1;
            int now = (lenA > lenB ? lenA : lenB) - 1;
            boolean overFlag = false;
            // a 和 b 相加
            for (; i >= 0 && k >= 0; i--, k--, now--) {
                int sum = (a.charAt(i) - '0') + (b.charAt(k) - '0');
                sum += overFlag ? 1 : 0;

                overFlag = sum >= 2;
                ch[now] = (char) ((sum % 2) + '0');
            }

            // 将 a 和 b 中长的放到ch中，但是要注意进位
            for (int n = now; n >= 0; n--) {
                int sum;
                if (lenA > lenB) {
                    sum = a.charAt(n) - '0';
                } else {
                    sum = b.charAt(n) - '0';
                }

                sum += overFlag ? 1 : 0;
                overFlag = sum >= 2;
                ch[n] = (char) ((sum % 2) + '0');
            }

            // 如果最后还有进位，则要再加字符1
            String str = new String(ch);
            if (overFlag) {
                str = "1" + str;
            }
            return str;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) {
        String a = "111";
        String b = "1";
        Solution solution = new P67AddBinary().new Solution();
        System.out.println(solution.addBinary(a, b));
        // TO TEST
    }

}